Emping-0.5: doc/user guide/empug-local.html
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<meta name="generator" content="Bluefish 1.0.7">
<title>Emping User Guide, Version 0.5</title>
</head>
<body bgcolor="white" text="black">
<p align="center"></p>
<center>
<h1>Emping User Guide, Version 0.5</h1><font size=
"4"><i>Author: Hans van Thiel, April 2008</i><br>
email: hthiel.char@zonnet.nl</font>
</center>
<h1>New in Version 0.5</h1>
<ul>
<li>The partial order of reduced rules is now displayed as graphs in Graphviz format.</li>
<li>Reduced rules and equivalence groups are sorted by length.</li>
<li>The GUI has been improved.</li>
</ul>
<h1>1. Overview</h1>
<h2>1.1. What</h2>
<p>Emping is a utility that derives heuristic rules from nominal
data. Nominal data are qualitative and unordered, as in:</p>
<ul>
<li>Color: red, green, blue, yellow, black</li>
<li>Proposition 1: True, False</li>
<li>Class: A,B,C,D</li>
</ul>
<p>Class is actually an ordinal attribute, but when the order is
disregarded, it is nominal.</p>
<p>Heuristic rules consist of attribute values (predicates) that
together imply another attribute value. For example:</p>
<dl>
<dt>Color: green and Proposition 1: True is Class: B</dt>
</dl>
<p>Heuristic rules are purely empirical, with no foundation in a
theory or model. The input of Emping is just a table of nominal
facts. The user has to select which attribute is to be the
consequent. Then Emping derives all shortest combinations of factors which, in the
table, imply the values of the selected consequent.</p>
<p>Each reduced rule is a generalization of one or more original rules, and
therefore reduced rules may imply other reduced rules or be
equivalant to others. So the reductions are partially ordered, and this partial order
can be shown in a directed graph.</p>
<h2>1.2. How</h2>
<p>Emping reads a file in a comma seperated format (.csv) as
produced by the Open Office Calc spreadsheet, and returns the
results as .csv files that can be read by OO Calc. The graphs are in Graphviz format,
and can be displayed by a Graphviz reader like dotty or ZRG Viewer.</p>
<p>Emping 0.5 has a GUI and you can start it like any other application.</p>
<p><img align="middle" src="./ugimg/Emping.png" alt="Emping" /> </p>
<p>The general idea is straightforward; see the screenshots for details. First,
you mark or unmark in the options menu whether you want to check the data for duplicates.
These have no effect on the result, but will slow the program down, and they are automatically removed
if the option is selected (but not from the source file itself). If there are duplicates you
can see which, with their frequencies, by saving them. </p>
<p>Next you select the consequent attribute from a popup menu. If you have the relevant options menu item
checked, emping will look for ambiguous rules for the selected consequent.</p>
<p>Ambiguous rules are rules which are exactly the same, except for the consequent value. For example,
an animal name may not be uniquely determined by a given description, only a group of animals.
So the result is indecisive for all possible subsets of this description, as well as the longer original.
The solution is to merge these rules with a new value, which denotes the union of the ambiguous rules,
the group.</p>
<p>However, it is possible to leave ambiguities in the data, as they will just cancel each other out.
But if all rules for some consequent value are ambiguous, there will be no rules at all for this value,
and this will result in a program error which blocks Emping. (See known bugs and issues.) </p>
<p>Therefore it is recommended to run Emping only with no duplicates and unambiguous rules,
though you can omit the checks, if you want, at your own risk.</p>
<p>See the white paper <i>Deriving Heuristic Rules from Facts</i> for more.</p>
<p>Pressing the Reduce button will start the actual reduction.</p>
<p>Reduced rules may themselves imply, or be equivalent to, other reduced rules with the same consequent value.
The Top button will produce only the top level of these rules (saved in a .csv file).</p>
<p>The reduced normal form file, the top level rule file and the others (if present),
can now be loaded into OO Calc.</p>
<p>To see the partial order in Graphviz graphs you must first get the graph legend. This file, in .csv format,
shows the nodes in the first column and the equivalence groups it denotes in the following rows. The
legend is useful in itself because, unlike the top level only file, it shows all reduced rules
grouped as equals.</p>
<p>Now you can construct the graph for all attributes and also separate graphs for each value of the attribute.
The reverse option lets you choose between the most general at the top(default),
or the most specific at the top (reversed).</p>
<h1>2. Known bugs and issues</h1>
<ul>
<li>If you run Emping with no ambiguity check, and ALL rules for some consequent attribute value
are ambiguous, the program will stall. In the mushrooms file, for example, it turns out
that all 292 kinds of mushroom, which grow in meadows, grow somewhere else too. Therefore there
are no rules that determine whether a mushroom grows in a meadow or not, and the reduction result
for <i>meadows</i> (consequent attribute <i>Habitat</i> is empty. In the current version this results in
a program error, and the main loop will go to sleep. If there are no ambiguous rules, this situation
cannot occur; there will always be at least one rule for <i>Habitat : meadows</i> .</li>
<li>The ambiguity check does not distinguish duplicates (equal facts) from true ambiguities
(equal antecedent, different consequent). So, if you run the ambiguity check, run the duplicate check too.</li>
<li>If you run the same radio button selection consequently, for example the default and the reversed
value graph, nothing will happen. This is because the action is triggered by a change in selection.
A workaround is to select another choice, cancel, and then select the first again.</li>
<li>If the duplicates and ambiguities checks finish very quickly, the appearance of the file
chooser window blocks the status message. This could easily confuse the user, who gets no special message
that it is the duplicates/ambiguities which will be saved, not the reductions.
</li>
</ul>
<h2>Some Example Screenshots</h2>
<p>An Open Office Calc data file:</p>
<p><img align="middle" src="./ugimg/Mushrooms_Data.png" border="0" alt=
"Mushrooms Data in OO Calc"></p>
<ul>
<li>The first row must list the attribute names. It is recommended
you give each a unique name, but you can use duplicates and blanks.
The columns below each attribute name list the values for that attribute, possibly blanks.
<li>Each value name has its column as its scope, so you can use values "Yes" and "No",
for example, for different attributes.</li>
<li>A blank value field stands for "none of the others". This feature is new to version 0.4.
Using blanks you can now use Emping on data sets which have splits on some values. For example,
an attribute "owns a car" can be 'yes" and 'no", and then "yes" can have fields on price range, make,
and so on, with field "no" blank on those values. This feature has, at the time of writing,
only be tested on small hypothetical data sets.</li>
<li>You can select an attribute with blank fields as the consequent. Because a blank field
stands for "none of the others" or "not applicable", rules with a blank consequent value
will automatically be removed from the rule set before the reduction is applied.</li>
<li>you can use integral numbers, like 0, 1, 3, 22 etc., but they
will be treated as nominal values, just like A,B,C etc.</li>
<li>Save the spreadsheet table in Text CSV format. Choose double quotes as the
text delimiter (default). Integral numbers will be stored without
delimiters, and emping will use them after checking if they are
all digits (no negatives, no fractions). Names within quotes
should not contain special characters, only letters, possibly
numbers and white space.</li>
</ul>
<p>The reduction of the <i>Mushrooms</i> data set with <i>Class</i> as the consequent. </p>
<p><img align="middle" src="./ugimg/Mushrooms_Class_Reds.png" alt="Mushrooms reduced rules in OO Calc" /> </p>
<p>It turns out there are 21 single attribute values that determine whether a mushroom is poisonous,
and 23 whether it is edible. But Emping also finds all combinations of two, of three, etc.
It is easy to verify these rules in the original data by using the Data Filter tool in OO Calc.</p>
<p>The most general rules only (Tops) for a data file of zoo animals with <i>Type</i> as the consequent.</p>
<p><img align="middle" src="./ugimg/Zoo_Type_Tops.png" border="0" alt="most general rules for zoo Type" /></p>
<p>It turns out the 824 reduced rules all imply 9 equivalence classes. Type 1 is completely determined by
the <i>Milk : yes</i> value only. The dependency graph for this value, however, shows some very complicated
entailments (not shown here).</p>
<p>The graph legend for a medical file of 200 audiology patients, 71 classes of symptoms
and 24 types of diagnosis. Each patient is anonymously identified by a letter and a number.</p>
<p><img align="middle" src="./ugimg/Audiology_Class_GLegend.png" border="0"
alt="Audiology Class graph Legend" /></p>
<p>Each of the 1200 nodes identifies clusters of symptoms that predict a specific diagnosis.
The attribute graph is very large and complex, but there are distinct differences for each diagnosis.</p>
<p>This is the value graph for <i>conductive discontinuity</i>, viewed with the
dotty viewer and editor which comes with Graphviz. </p>
<p><img align="middle" src="./ugimg/Conductive_discontinuity-dotty.png" border="0"
alt="Audiology value graph conductive discontinuity" /></p>
<p>The first number is the node, the second the number of equivalences in that node.
All graphs (for the same attribute) use the same legend.</p>
<p>The situation is very different, however, for <i>cochlear age and noise</i> .</p>
<p><img align="middle" src="./ugimg/cochlearageandnoise_large_zrgviewer.png"
border="0" alt="Audiology Cochlear age and noise ZRG Viewer" /></p>
<p>This image has been produced by ZRG Viewer, a viewer dat works with Graphviz
and produces scaleable vector graphic (.svg) images. This is a zoom in on some nodes in the same graph.
Using dotty or ZRG Viewer you can trace paths and analize the relations in detail.</p>
<p><img align="middle" src="./ugimg/cochlearageandnoise_zoom_zrgviewer.png"
border="0" alt="Audiology Cochlear age and noise zoom inZRG Viewer" /></p>
<p>As before, the first number refers to the node in the legend, the second to the
number of equivalent classes. To recall, each member of an equivalence class is a
different generalization of the same original rules (rows) from the data table.</p>
<p>Finally, here is the graph for <i>bellspalsy</i> ,this time in dotty again.</p>
<p><img align="middle" src="./ugimg/bellspalsy_dotty.png"
border="0" alt="Bellspalsy" /></p>
<p>It turns out there is only one patient with this diagnosis in the data file. This
is p77, uniquely identified by the symptom <i>viith_nerve_signs : yes</i> . However,
there appear to be 561 more clusters of symptoms that define this patient and diagnosis.</p>
<h1>Data Files</h1>
<p>The examples shown are from the data files Zoo, Mushrooms and Audiology,
all available at the <a href="http://archive.ics.uci.edu/ml/">UCI Machine Learning Repository</a> .
Thanks to: Asuncion, A. & Newman, D.J. (2007). UCI Machine Learning Repository
[http://www.ics.uci.edu/~mlearn/MLRepository.html].
Irvine, CA: University of California, School of Information and Computer Science.</p>
<h1>Notes</h1>
<p>The Emping utility is written in Haskell, and has been developed and tested on the Fedora Core Linux platform,
using the Haskell tools which are available as FC packages. Version 0.5 has been developed on FC8 with GHC 6.8.2
and Gtk2Hs 0.9.12. Earlier versions of GHC will probably not compile, and Gtk2Hs versions earlier than 0.9.12
don't support the implemented menu fields, and will not work.
<p>But GHC and Gtk2Hs are implemented on many platforms, including Windows and Linux versions, so
Emping-0.5 should work on those platforms too. Open Office Calc, Graphviz and ZRGViewer (which depends
on Graphviz) are open source and widely available.</p>
<p>The time needed to perform a reduction or to produce a graph is hard to predict, since
they depend on the complexity as well as the size of the data. In the examples, the shortest
time was for the zoo animals (a few seconds) and the longest for the mushrooms attribute graph (45 minutes).</p>
<p>The reduction should be, and appears to be, linearly proportional to the number of rules, but the
graph building process tests each reduction against each original rule. The complexity of that is quadratic.
The reduction time is, at least, a multiple of the number of values in the consequent class.</p>
<p>Any comments, bug reports, feature requests or remarks will be
most welcome.</p>
<p><i>Emping</i> stands for <i>empirical reasoning</i> or the
Indonesian snack with that name.</p>
</body>
</html>